The present invention relates to a circuit for correcting an approximate quotient in a data processor which adopts a division method for obtaining an approximate quotient by repeated multiplications.
In obtaining a quotient q=N/D where N denotes a dividend and D denotes a divisor, the method puts: ##EQU1## and finds R.sub.0, R.sub.1, R.sub.2, . . . bringing D.times.R.sub.0 .times.R.sub.1 .times.R.sub.2 .times. . . . close to 1 (one), thereby to obtain: EQU q.apprxeq.N.times.R.sub.0 .times.R.sub.1 .times.R.sub.2 .times.(2)
The first R.sub.0 is the approximate value of the reciprocal of D, and is obtained from a table which stores R.sub.0 in a pair with D in advance. Letting D.times.R.sub.0 =1-.epsilon. and 0.ltoreq..vertline..epsilon..vertline.&lt;1, R.sub.1 is obtained by: EQU R.sub.1 =2-D.times.R.sub.0 =1+.epsilon. (3)
and the following holds: EQU D.times.R.sub.0 .times.R.sub.1 =(1-.epsilon.)(1+.epsilon.)=1-.epsilon..sup.2 ( 4)
Subsequently, putting R.sub.2 =2-D.times.R.sub.0 .times.R.sub.1 =1+.epsilon..sup.2, the following holds: EQU D.times.R.sub.0 .times.R.sub.1 .times.R.sub.2 =(1-.epsilon..sup.2)(1+.epsilon..sup.2)=1-.epsilon..sup.4 ( 5)
By repeating such operations, D.times.R.sub.0 .times.R.sub.1 .times.R.sub.2 .times. . . . .times.R.sub.n .fwdarw.1 can be established. Assuming now that .epsilon..sup.4 has become less than or equal to the number of significant digits finally required for a quotient, EQU q'=N.times.R.sub.0 .times.R.sub.1 .times.R.sub.2 ( 6)
is the approximate quotient to be found.
In case of obtaining the quotient with the above method, ##EQU2## holds, or EQU N.times.R.sub.0 .times.R.sub.1 .times.R.sub.2 =q(1-.epsilon..sup.4) (8)
holds. Therefore, when q'=N.times.R.sub.0 .times.R.sub.1 .times.R.sub.2 is deemed the quotient, an error of q.times..epsilon..sup.4 develops between the approximate quotient q' and the true quotient q. For this reason, even when the true quotient q is a divisible value, the approximate quotient q' is indivisible in some cases. Accordingly, even when the true quotient q is the divisible value, the approximate solution q' can become unequal to the true value. (With a method performing a division by repeating subtractions, a quotient equal to the true quotient q is obtained whenever the latter is divisible.) Accordingly, the approximate solution q' obtained with the division method employing the reciprocal as above stated needs to be corrected in order that a quotient equal to the true quotient q may be obtained infallibly when the latter is the divisible value.
The approximate quotient q' is expressed by q'=q (1-.epsilon..sup.4), and the multiplications need to be repeated until q.times..epsilon..sup.4 becomes a value smaller than the least significant bit of the quotient. Hereinbelow, the division of data in the floating point notation will be described unless otherwise specified. In this case, subtractions are performed as to an exponent part, and a division is performed as to a fraction part. In the following, accordingly, the fraction part of the dividend N shall be simply called the "dividend N", while that of the divisor D shall be simply denoted by the divisor D, and the fraction part of the true quotient q shall be simply denoted by the true quotient q, while that of the approximate quotient q' shall be simply called the "approximate quotient q'". It is now supposed that the number of significant digits of the fraction part of the floating point data is m, and that the approximate quotient q' is evaluated at a precision of (m+n) digits so that the value of q.times..epsilon..sup.4 may become smaller than the value of a place which is n digits (n.gtoreq.1) still lower than the least significant bit in the floating point notation. At this time, there is the possibility that an error of .+-.1 will occur at the (m+n)-th digit. Whether the error becomes 0, +1 or -1, depends upon the data directed toward the division.
Here, the value of the m significant digits of the true quotient q is denoted by q.sub.m. Further, as shown in FIG. 1, the value of the upper m digits of the approximate quotient q' obtained at the precision of the (m+n) digits is denoted by Q.sub.m, while the value of the (m+n) digits, including extra n digits, of the approximate quotient q' is denoted by Q.sub.m+n.
When the error is 0 (zero), q.sub.m =Q.sub.m holds, and any correction is unnecessary.
When the error is +1, 1 (one) needs to be subtracted from the lowest digit of Q.sub.m+n. This subtraction causes a change in Q.sub.m only in a case where the extra n digits are all `0`. At this time, a correction of Q.sub.m -2.sup.-m is necessary.
When the error is -1, 1 (one) needs to be added to the lowest digit of Q.sub.m+n. This addition causes a change in Q.sub.m only in a case where the extra n digits are all "1". At this time, a correction of Q.sub.m +2.sup.-m is necessary.
Accordingly, the correction is required only in the case where the n digits obtained in excess of the m significant digits in the floating point notation are all `0` or all `1`.
Which of 0, +1 and -1 conditions of error occur, depends upon the data and is difficult to determine in the course of the division processing. Therefore, the following correction method has heretofore been adopted.
By repeating the multiplications to the precision at which the error develops at the place which is n digits lower than the m significant digits, an approximate quotient Q.sub.m+n consisting of the (m+n) digits is obtained. A value obtained by adding 1 (one) to the lowest digit ((m+n)-th digit) of Q.sub.m+n and discarding places below the m-th digit, is provided as a corrected approximate quotient Q.sub.H. As a result, the correction in the case where the error is -1 and where the extra n digits are all `1` can be made. When the extra n digits are neither all `0` nor all `1`, q.sub.m of the true quotient q and Q.sub.m become equal as in the case where no correction is made.
By performing this correction, when the true quotient is the divisible value, the final approximate solution is ensured to become equal to the true quotient. However, all the corrections are not covered, but the corrected approximate quotient Q.sub.H becomes greater than the true value in (1) a case where the extra n digits are all `1` and where the error of 0 or +1 exists and (2) a case where the extra n digits are all `0` and where the error of +1 exists. As a result, a problem to be stated below arises. With the hitherto known method which evaluates the quotient by repeating the subtractions, the sign of a remainder is identical to that of the dividend. For example, in a case where both the dividend N and the divisor D are plus, N-(approximate quotient).times.D.gtoreq.0 is ensured. In contrast, the foregoing correction of +1 before the discard results in that N-(approximate quotient).times.D&lt;0 can take place.
In order to avoid this drawback, Q.sub.H obtained by the foregoing correction is further subjected to the following correction (Japanese Patent Application Laying-open No. 54-162936):
(1) When the extra n digits are neither all `0` nor all `1`, Q.sub.H is provided as the final quotient.
(2) When the extra n digits are all `0` or all `1`, EQU R=N-Q.sub.H .times.D (9)
is calculated at a precision of 2.multidot.m digits being double the number m of the floating-point significant digits. For R.gtoreq.0, Q.sub.H is provided as the final quotient, and for R&lt;0, Q.sub.H -2.sup.-m is provided as the final quotient.
By performing the two stages of correction processing as stated above, the same result as in the method finding the quotient by repeating the subtractions has been obtained.
Such correction system hitherto used for obtaining the correct quotient in the division method which finds the approximate quotient by repeated multiplications, does not take into account the desire to process the division of vector data at high speed with a pipeline. In introducing the prior-art correction system into the pipeline processing, the following problems are posed.
First, the comparing operation of N-Q.sub.H .times.D 0 needs to be carried out at the precision double the number m of the significant digits in the floating point notation, so that an adder at the precision of the 2.multidot.m digits needs to be provided. Moreover, signal lines for the delivery of data at double precision are required between the adder of double precision and a multiplier for executing Q.sub.H .times.D.
Secondly, the correction system hitherto used does not take the pipeline processing into consideration, and a multiplier required for the correction processing and a multiplier for calculating the approximate quotient Q.sub.H are common in many cases. In order to perform the correction processing with the pipeline continuously with the calculation of the approximate quotient Q.sub.H, a plurality of multipliers are necessary. In a data processor having an insufficient number of multipliers, the processing for calculating the approximate quotient Q.sub.H and the correction processing of the approximate quotient Q.sub.H cannot be executed continuously, and there is required the processing of once writing the approximate quotient Q.sub.H into a storage device or the like and making the correction by reading it out again. In this case, in order to perform the correction processing with the pipeline, the operation of N-Q.sub.H .times.D is required as to the dividend N, the approximate quotient Q.sub.H and the divisor D, and the three elements consisting of the dividend N, the divisor D and the approximate quotient Q.sub.H need to be entered into an arithmetic unit. This also brings about the problem that a conventional arithmetic unit having 2 inputs and 1 output, and instructions of the format which appoints 2 input operands and 1 output operand with one instruction cannot be used as they are. Moreover, in the case where the calculation of the approximate quotient and the correction processing thereof are not performed continuously and where the correction processing is executed by once writing the approximate quotient Q.sub.H into the storage device or the like and reading it out again, the data of the extra n digits obtained at the stage of the calculation of the approximate quotient needs to be kept stored in the storage device or the like because they are required for deciding the necessity for the correction processing, so that surplus data areas are necessary. Especially in a vector processor of the type which stores operation data in a vector register, there occurs the problem that the capacity of the vector register must be made large.